package DFS;

import java.util.Arrays;

/**
 * @Author Fizz Pu
 * @Date 2020/9/11 下午7:33
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class DfsMatrix {
    /**
     * 使用dfs遍历矩阵,采用递归编写
     * 遍历的过程中，有些元素访问过了,因此要么把遍历过的元素保存下来，要么更改值
     * 规定这个矩阵的元素全是正整数，而且元素可重复，遍历过了就把元素改为0
     * 这里我按照左 ——> 右 ——> 下 ——> 上的方向遍历
     * 这个就是典型的迷宫问题，当然迷宫也有最短路径迷宫和dfs写的迷宫，有空可以做成一个小游戏出来，可以生成地图
     * @param matrix 二维数组
     * @param row 开始遍历的那个元素的行
     * @param col 开始遍历的那个元素的列
     */
    public static void dfs(int[][] matrix, int row, int col){
        if(matrix == null)return;

        // 赋值数组，取总结java中复制数组的方法和效率
        int[][] land = new int[matrix.length][];
        for(int i = 0; i < land.length; ++i){
            land[i] = Arrays.copyOf(matrix[i], matrix[i].length);
        }

        // 越界，元素已经被访问则回退
        if(row < 0 | row > land.length - 1 | col < 0 | col > land[0].length - 1 | land[row][col] ==0 ){
            return;
        }

        System.out.print(land[row][col]);
        System.out.print(", ");
        matrix[row][col] = 0;
        dfs(land, row, col + 1); // 左走
        dfs(land, row, col - 1); // 右走
        dfs(land, row + 1, col); // 下走
        dfs(land, row - 1, col ); // 上走
    }
}
